# Kuhn Munkres：不断在相等子图中，利用广度优先搜索每个点的增广路，直到形成完美匹配

import numpy as np
from tools.Conversion import Conversion
from tools.Input import Input
from tools.Output import Output


class KM:
    __name = 'Kuhn Munkres'

    @staticmethod
    def do_km():
        # g = Input.input_bipartite_graph()  # 输入二部图
        g = Conversion.bipartite_graph_arr_2_matrix(Input.get_complete_bipartite_graph())  # 获取一个图（例5.5.1）
        print('输入的图为：')
        Output.print_bipartite_graph_matrix(g)

        v_set1 = g[0][0]
        v_set2 = g[0][1]  # 点集
        s_set = g[1]  # 边集（邻接矩阵）

        match_set = {}  # 匹配（key:v_set2，value:v_set1）

        searched_path = []  # 增广路

        v_set1_mark = [max(s) for s in s_set]  # v_set1的顶标
        v_set2_mark = [0 for i in range(len(v_set2))]  # v_set2的顶标

        print('生成过程：')
        print('初始顶标：')
        print(v_set1_mark, v_set2_mark)
        while True:
            if len(v_set1) == len(match_set):
                break

            print('l等子图：')
            Output.print_bipartite_subgraph_matrix(g=g, marks=[v_set1_mark, v_set2_mark])

            for v1_index in range(len(v_set1)):
                v1 = v_set1[v1_index]
                if v1 not in match_set.values():  # 找到不在匹配中的点
                    searched_path.clear()
                    find = KM.find_match(g, [v_set1_mark, v_set2_mark], v1_index, searched_path, match_set)  # 找匹配
                    if find and len(searched_path) > 2:  # 找到匹配
                        print('找到增广路', searched_path)

                    if not find:  # 没找到匹配
                        print('点', v1, '匹配失败')
                        if KM.update_mark(g, [v_set1_mark, v_set2_mark], searched_path) == 0:
                            print('无最优匹配')
                            return
                        print('更新顶标：')
                        print(v_set1_mark, v_set2_mark)
                        break

        print('最优匹配：')
        Output.print_match(match_set)
        print('最大权重：')
        print(sum(v_set1_mark) + sum(v_set2_mark))

    ''' 从v1中找匹配（深度优先遍历） '''

    @staticmethod
    def find_match(g, marks, v1_index, searched_path, v_set_match):

        v_set1 = g[0][0]
        v_set2 = g[0][1]  # 点集
        s_set = g[1]  # 边集（邻接矩阵）

        v_set1_mark = marks[0]  # v_set1的顶标
        v_set2_mark = marks[1]  # v_set2的顶标

        v1 = v_set1[v1_index]
        searched_path.append(v1)

        for v2_index in range(len(v_set2)):
            v2 = v_set2[v2_index]
            m = v_set1_mark[v1_index] + v_set2_mark[v2_index]
            if s_set[v1_index][v2_index] == m and m != 0 and v2 not in searched_path:  # 相等子图index不在增广路中的邻边
                searched_path.append(v2)  # 加入v2
                if v2 not in v_set_match.keys() or KM.find_match(g, [v_set1_mark, v_set2_mark],
                                                                 v_set1.index(v_set_match[v2]), searched_path,
                                                                 v_set_match):  # v2不在匹配中或v2匹配的点有增广路
                    v_set_match.update({v2: v1})  # 将v2:v1加入匹配
                    return True
        return False

    ''' 更新顶标 '''

    @staticmethod
    def update_mark(g, marks, enlarge_path):
        print("历史路径：", enlarge_path)
        v_set1 = g[0][0]
        v_set2 = g[0][1]  # 点集
        s_set = g[1]  # 边集（邻接矩阵）

        v_set1_mark = marks[0]  # v_set1的顶标
        v_set2_mark = marks[1]  # v_set2的顶标

        v_s = []  # 路径上v_set1的顶点集
        v_t = []  # 路径上v_set2的顶点集

        for v in enlarge_path:  # 把路径上的点添加到对应顶点集
            if v in v_set1:
                v_s.append(v)
            if v in v_set2:
                v_t.append(v)
        v1_find = v_s  # 需要遍历的v_s中点集合
        v2_find = np.setdiff1d(v_set2, v_t)  # 需要遍历的v_set2 - v_t中点集合
        print('S集合：', v_s)
        print('T集合：', v_t)

        d = float('Inf')  # 顶点调整值d，初始化为正无穷

        for v1 in v1_find:  # 遍历v1_find中的点
            index1 = v_set1.index(v1)
            l1 = v_set1_mark[index1]  # v1_find中点的顶标值
            for v2 in v2_find:  # 遍历v2_find的点
                index2 = v_set2.index(v2)
                l2 = v_set2_mark[index2]  # v2_find的顶点值
                w = s_set[index1][index2]  # v1_find到v2_find的权值
                d = min(l1 + l2 - w, d)  # 取最小值

        for v1 in v_s:  # v_s中的点 -d
            index1 = v_set1.index(v1)
            v_set1_mark[index1] = v_set1_mark[index1] - d
        for v2 in v_t:  # v_t中的点 +d
            index2 = v_set2.index(v2)
            v_set2_mark[index2] = v_set2_mark[index2] + d

        print('变化值α：', d)
        return d
